package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Backtracking;
import cn.pugle.oj.catalog.TreeProblem;

import java.util.*;

/**
 * https://leetcode.com/problems/word-search-ii/
 * 回溯+Trie树(LC208)
 *
 * LC79 word search 1
 * @author tzp
 * @since 2020/10/14
 */
public class LC212 implements TreeProblem, Backtracking {
    public static class TrieNode {
        public boolean isWordEnd;
        public Map<Character, TrieNode> children;

        public TrieNode() {
            this.isWordEnd = false;
            this.children = new HashMap<>();
        }
    }

    public static class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                cur.children.computeIfAbsent(word.charAt(i), character -> new TrieNode());
                cur = cur.children.get(word.charAt(i));
            }
            cur.isWordEnd = true;
        }


        public boolean search(String word) {
            TrieNode cur = root;
            for (int i = 0; i < word.length(); i++) {
                if (!cur.children.containsKey(word.charAt(i))) {
                    return false;
                } else {
                    cur = cur.children.get(word.charAt(i));
                }
            }
            return cur.isWordEnd;
        }

        public boolean startsWith(String prefix) {
            TrieNode cur = root;
            for (int i = 0; i < prefix.length(); i++) {
                if (!cur.children.containsKey(prefix.charAt(i))) {
                    return false;
                } else {
                    cur = cur.children.get(prefix.charAt(i));
                }
            }
            return cur != null;
        }
    }

    char[][] board;
    Trie trie;
    HashSet<String> result;
    boolean[][] path;

    public List<String> findWords(char[][] board, String[] words) {
        this.board = board;
        this.trie = new Trie();
        for (String word : words) {
            trie.insert(word);
        }
        this.path = new boolean[board.length][board[0].length];
        this.result = new HashSet<String>();
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                //注意, 可以重复使用, 所以不用判断是否visited, 不用判断是否在path里(废话path里啥也没有, 回溯都吐出去了!)
                backward(i, j, "");
            }
        }
        return new ArrayList<>(result);
    }

    static short[][] directions = new short[][]{
            {-1, 0}, {0, 1}, {1, 0}, {0, -1}//上右下左
    };

    public void backward(int x, int y, String prefix) {
        String curWord = prefix + board[x][y];//走到这里所组成的word/prefix
        if (trie.startsWith(curWord)) {
            if (trie.search(curWord)) {
                result.add(curWord);//找到了也要继续回溯, 不像别的直接return.
            }
            path[x][y] = true;//标记走过
            for (short[] direction : directions) {//四个选择
                int newX = x + direction[0];
                int newY = y + direction[1];
                if (inArea(newX, newY) && !path[newX][newY]) {//有效且没走过
                    backward(newX, newY, curWord);
                }
            }
            path[x][y] = false;//回溯, 退回标记
        }
        //没有startsWith的, 就不用继续回溯了
    }

    public boolean inArea(int x, int y) {
        return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
    }

    public static void main(String[] args) {
        char[][] a = {
                {'o', 'a', 'a', 'n'},
                {'e', 't', 'a', 'e'},
                {'i', 'h', 'k', 'r'},
                {'i', 'f', 'l', 'v'}
        };
        String[] b = {"oath", "pea", "eat", "rain"};
        System.out.println(new LC212().findWords(a, b));
    }
}
